package com.demo.datastructure.reorder.quickSort;

import com.demo.datastructure.reorder.Example;

/**
 * @description:
 * @author: ljr
 * @time: 2021/5/15 19:06
 */
public class SimlpeQuickSort implements Example {

    @Override
    public void sort(Comparable[] a, int low, int high) {
         if(low >= high) return;
         int mid = partition2(a, low, high);
         sort(a,low, mid-1);
         sort(a,mid+1,high);
    }

    private int partition(Comparable[] a, int low, int high) {
         int l = low, h = high-1;
         Comparable value = a[high];
         while(l < h){
             if(less(value, a[l])){
                 exch(a,l, h);
                 h--;
             }else{
                 l++;
             }
         }
         exch(a, ++h, high);
         return h;
    }

    private int partition2(Comparable[] a, int low, int high) {
        int l = low, min = low;
        Comparable value = a[high];
        for(int i = l; i < high; i++){
            if(less(a[l], value)){
                exch(a, l, min);
                min++;
            }
        }

        a[high] = a[min];
        a[min]  = value;
        return min;
    }


}
